#include <stdio.h>
#include <stdlib.h>

// 进程结构体
typedef struct {
    int id;             // 进程 ID
    int run_time;       // 执行时间
    int waiting_time;   // 等待时间
    int turnaround_time;// 周转时间
    int priority;       // 优先级
} PCB;

// 计算等待时间 (先来先服务)
void FCFS(int n, PCB pcb[]) {
    pcb[0].waiting_time = 0; // 第一个进程的等待时间为 0
    for (int i = 1; i < n; i++) {
        pcb[i].waiting_time = pcb[i - 1].run_time + pcb[i - 1].waiting_time;
    }
}

// 计算等待时间 (短作业优先)
void SJF(int n, PCB pcb[]) {
    int remaining_time[n]; // 剩余执行时间
    for (int i = 0; i < n; i++) {
        remaining_time[i] = pcb[i].run_time;
    }
    int complete = 0, t = 0, min = 10000;
    int shortest = 0, finish_time;
    int check = 0;
    while (complete != n) {
        for (int j = 0; j < n; j++) {
            if ((remaining_time[j] > 0) && (remaining_time[j] < min)) {
                min = remaining_time[j];
                shortest = j;
                check = 1;
            }
        }
        if (check == 0) {
            t++;
            continue;
        }
        remaining_time[shortest]--;
        min = remaining_time[shortest];
        if (min == 0) {
            min = 10000;
        }
        if (remaining_time[shortest] == 0) {
            complete++;
            check = 0;
            finish_time = t + 1;
            pcb[shortest].waiting_time = finish_time - pcb[shortest].run_time;
            if (pcb[shortest].waiting_time < 0) {
                pcb[shortest].waiting_time = 0;
            }
        }
        t++;
    }
}

// 计算等待时间 (高响应比优先)
void HRRN(int n, PCB pcb[]) {
    int completed = 0, t = 0, max_index;
    float max_response_ratio, response_ratio;
    int is_completed[n];
    for (int i = 0; i < n; i++) {
        is_completed[i] = 0;
        pcb[i].waiting_time = 0;
    }
    while (completed != n) {
        max_response_ratio = -1;
        for (int i = 0; i < n; i++) {
            if (is_completed[i] == 0) {
                response_ratio = (float)(t + pcb[i].run_time) / pcb[i].run_time;
                if (response_ratio > max_response_ratio) {
                    max_response_ratio = response_ratio;
                    max_index = i;
                }
            }
        }
        t += pcb[max_index].run_time;
        pcb[max_index].waiting_time = t - pcb[max_index].run_time;
        is_completed[max_index] = 1;
        completed++;
    }
}

// 计算等待时间 (优先级调度)
void PSA(int n, PCB pcb[]) {
    // 假设优先级数值越小表示优先级越高
    int completed = 0, t = 0;
    int highest_priority, highest_index;
    int is_completed[n];
    for (int i = 0; i < n; i++) {
        is_completed[i] = 0;
        pcb[i].waiting_time = 0;
    }
    while (completed != n) {
        highest_priority = 9999; // 初始一个很大的值
        for (int i = 0; i < n; i++) {
            if (is_completed[i] == 0 && pcb[i].priority < highest_priority) {
                highest_priority = pcb[i].priority;
                highest_index = i;
            }
        }
        t += pcb[highest_index].run_time;
        pcb[highest_index].waiting_time = t - pcb[highest_index].run_time;
        is_completed[highest_index] = 1;
        completed++;
    }
}

// 计算周转时间
void countTurnAroundTime(int n, PCB pcb[]) {
    for (int i = 0; i < n; i++) {
        pcb[i].turnaround_time = pcb[i].run_time + pcb[i].waiting_time;
    }
}

// 计算平均时间
void countAvgTime(void (*findWaitingTime)(int, PCB[]), int n, PCB pcb[]) {
    float total_wait = 0, total_turnaround = 0;
    findWaitingTime(n, pcb); // 计算等待时间
    countTurnAroundTime(n, pcb); // 计算周转时间
    printf("  进程        执行时间        等待时间        周转时间\n");
    for (int i = 0; i < n; i++) {
        printf("   %d \t\t %d \t\t %d \t\t %d\n", pcb[i].id, pcb[i].run_time, pcb[i].waiting_time, pcb[i].turnaround_time);
    }
    for (int i = 0; i < n; i++) {
        total_wait += pcb[i].waiting_time;
        total_turnaround += pcb[i].turnaround_time;
    }
    printf("平均等待时间 = %f\n", total_wait / n);
    printf("平均周转时间 = %f\n", total_turnaround / n);
}

int main() {
    system("clear");
    int choice, n;
    while (1) {
        printf("**********菜单**************\n");
        printf("选择调度算法：\n");
        printf("1. 先来先服务 (FCFS)\n");
        printf("2. 短作业优先 (SJF)\n");
        printf("3. 高响应比优先 (HRRN)\n");
        printf("4. 优先级调度 (PSA)\n");
        printf("5. 退出\n");
        printf("****************************\n");
        printf("输入你的选择： ");
        scanf("%d", &choice);
        if (choice == 5) {
            break; // 退出循环
        }
        if (choice < 1 || choice > 5) {
            printf("无效的选择，请重新选择\n");
            continue;
        }
        printf("输入进程数量： ");
        scanf("%d", &n);
        if (n <= 0) {
            printf("无效的进程数量，请重新选择\n");
            continue;
        }
        PCB pcb[n];
        printf("输入进程的执行时间和优先级 (优先级仅用于 PSA 算法)：\n");
        for (int i = 0; i < n; i++) {
            printf("进程 %d: ", i + 1);
            scanf("%d %d", &pcb[i].run_time, &pcb[i].priority);
            pcb[i].id = i + 1;
        }
        switch (choice) {
            case 1:
                countAvgTime(FCFS, n, pcb);
                break;
            case 2:
                countAvgTime(SJF, n, pcb);
                break;
            case 3:
                countAvgTime(HRRN, n, pcb);
                break;
            case 4:
                countAvgTime(PSA, n, pcb);
                break;
        }
    }
    return 0;
}
